package 二分法;


/**
 * @author： li
 * @date： 2022-01-16 16:11
 * @version 1.0
 */

/*问题描述
　　住在有顶天的天人Tensi对自己的住处很不满。终于有一天她决定把门前碍眼的要石通通丢掉（怒扔要石）。控制要石自然是很容易的事，
   不过也会消耗灵力。假设搬走一块质量为1的要石会消耗1点灵力，而且由于要石都是连着放置的缘故所以每次除了搬走一颗，
   也可以搬走连续的任意数量的要石，自然质量是算在一起的。现在Tensi准备最多使用M次灵力，但是她太懒……所以每次只会使用同量的灵力，
   也因为她太烂，所以也不愿意多花一点灵力……现在很懒的Tensi需要你帮她计算最少一次需要消耗多少灵力，能够在M次内把所有要石都丢到人间去……
输入格式
　　第一行两个数N,M，用一个空格分隔。1<=n<=1000,1<=m<=400
　　表示一共有N颗要石需要搬走已经Tensi最多发动M次灵力。
　　接下来包括N 个正整数 0<=ai<=40000 顺序表示每一颗要石的质量。
输出格式
　　输出一个数T
　　表示Tensi 每次至少消耗T灵力。0<=T<=1000000
　　如果无解输出-1.
样例输入
5 3
1 2 1 1 1
样例输出
3
数据规模和约定
　　对于100%的数据，1<=n<=1000，1<=m<=400，0<=ai<=40000。
　　保证0<=T<=1000000。
 */
import java.util.ArrayList;
import java.util.Scanner;
public class 搬走要石 {
    static int n,m;
    static int count=0;
    static ArrayList<Long> t = new ArrayList<>();
    static ArrayList<Long> panduan(int ll, int rr, int mide, int[] a) {
        long sum_l = 0, sum_r = 0, sum = 0, max = 0, sum1 = 0;
        int pos = 0;
        for (int i = ll; i <=mide; i++) {
            sum_l = sum_l + a[i];
        }
        for (int i = mide; i <=rr; i++) {
            sum_r = sum_r + a[i];
        }
        System.out.println("sum_l:" + sum_l);
        System.out.println("sum_r:" + sum_r);
//        max=sum_l;
        if(sum_l!=0&&sum_r!=0){
        max = Math.min(sum_l, sum_r);
        System.out.println("max:" + max);
        for (int i = 0; i < n; ) {
            if (a[0] > max) break;
            sum = sum + a[i];
            i++;
            if (sum > max) {
                i = i - 1;
                sum = 0;
                count += 1;
                pos = Math.max(i, pos);
//                    System.out.println("i:"+i);
            }
            if (sum == max) {
                sum = 0;
                count += 1;
                pos = Math.max(i, pos);
//                    System.out.println("i:"+i);
            }
            if (i == n - 1) break;
        }
        for (int i = pos; i <= n; i++) {
            sum1 = sum1 + a[i];
        }
        if (sum1 < max && sum1 != 0) {
            count = count + 1;
        } else if(sum1>max&&sum1!=0){
            count = count + 2;
        }
        System.out.println("pos:" + pos);
        System.out.println("count:" + count);
        if (count <= m && max <= 1000000 && count >= 1) {
            t.add(max);
        }
        count = 0;
        if(rr+1>n-1||ll-1<0) return t;
        if (sum_l<=sum_r) {
            ll = mide;
            rr =rr+1;
        } else {
            rr = mide;
            ll = ll-1;
        }
        mide = (ll + rr) / 2;

        panduan(ll, rr, mide, a);
    }
        return t;
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int[] ai;
        n = sc.nextInt();
        m = sc.nextInt();
        ai = new int[n + 1];
        ArrayList<Long> res;
        long result = Integer.MAX_VALUE;
        for (int i = 0; i < n; i++) {
            ai[i] = sc.nextInt();
        }
        int l = n/2-1, r = n/2+1, mid = n / 2;
        res = panduan(l, r, mid, ai);
        System.out.println(" ");
        if (res.isEmpty()) {
            System.out.println(-1);
        } else {
            for (long i : res)
                System.out.print(i + " ");
            System.out.println(" ");
            for (long i : res) {
                result = Math.min(result, i);
            }
            System.out.println(result);
        }
    }
}
